package _interview75;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 649. Dota2 参议院
 */
public class No649 {
    public String predictPartyVictory(String senate) {
        int n = senate.length();

        Queue<Integer> rDeque = new ArrayDeque<>();
        Queue<Integer> dDeque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            if (senate.charAt(i) == 'R') rDeque.offer(i);
            else dDeque.offer(i);
        }
        while (!rDeque.isEmpty() && !dDeque.isEmpty()) {
            Integer r = rDeque.poll();
            Integer d = dDeque.poll();
            if (r < d) rDeque.offer(n + r);
            else dDeque.offer(n + r);
        }
        return rDeque.isEmpty() ? "Dire" : "Radiant";
    }
}
